<?php

require_once './Base.php';

/**
 * 选择排序
 * 空间复杂度是1,额外的只占用了$min
 * 时间复杂度外层需要走n-1轮，最后一个不需要对比；内层n-j。大致是n*n
 */
class SelectSort extends BaseSort
{
	function select($arr)
	{
		$total = count($arr);
		$this->echoOnline($arr);
		for($j = 0; $j< $total - 1; $j++) {
			$index = $j;
			for($i = $j + 1; $i < $total; $i++) {
				if ($arr[$index] > $arr[$i]) {
					$index = $i;
				}
			}
			$min = $arr[$index];
			$arr[$index] = $arr[$j];
			$arr[$j] = $min;
			$this->echoOnline($arr);
		}
		$this->echoOnline($arr);
	}	
}